package org.algorithm.Sort;

import org.leetcode.easy.leetcode169.Solution;

public class MergeSort3 {

    public void mergeSort(int [] array){

        int n = array.length;

        int [] helper = new int[n];

        split(array,0,n-1,helper);
    }

    private void split(int [] array,int left,int right,int [] helper){
        if (left==right){
            return;
        }

        int mid = (left+right)>>>1;

        split(array,left,mid,helper);
        split(array,mid+1,right,helper);

        merge(array,left,mid,mid+1,right,helper);

        System.arraycopy(helper,left,array,left,right-left+1);
    }

    private void merge(int [] array,int i ,int iEnd,int j,int jEnd,int[] helper){

        int curr=i;

        while (i<=iEnd && j<=jEnd){
            if (array[i]<array[j]){
                helper[curr]=array[i];
                i++;
            }else {
                helper[curr]=array[j];
                j++;
            }
            curr++;
        }


        if (i>iEnd){
            System.arraycopy(array,j,helper,curr,jEnd-j+1);
        }

        if (j>jEnd){
            System.arraycopy(array,i,helper,curr,iEnd-i+1);
        }

    }

    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6, 7};

        MergeSort3 test = new MergeSort3();
        test.mergeSort(array);
        for (int i : array) {
            System.out.print(i + " ");
        }
    }

}
